home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / include / linux / jhash.h < prev    next >
C/C++ Source or Header  |  2005-10-13  |  3KB  |  144 lines
  1. #ifndef _LINUX_JHASH_H
  2. #define _LINUX_JHASH_H
  3.  
  4. /* jhash.h: Jenkins hash support.
  5.  *
  6.  * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
  7.  *
  8.  * http://burtleburtle.net/bob/hash/
  9.  *
  10.  * These are the credits from Bob's sources:
  11.  *
  12.  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
  13.  * hash(), hash2(), hash3, and mix() are externally useful functions.
  14.  * Routines to test the hash are included if SELF_TEST is defined.
  15.  * You can use this free for any purpose.  It has no warranty.
  16.  *
  17.  * Copyright (C) 2003 David S. Miller (davem@redhat.com)
  18.  *
  19.  * I've modified Bob's hash to be useful in the Linux kernel, and
  20.  * any bugs present are surely my fault.  -DaveM
  21.  */
  22.  
  23. /* NOTE: Arguments are modified. */
  24. #define __jhash_mix(a, b, c) \
  25. { \
  26.   a -= b; a -= c; a ^= (c>>13); \
  27.   b -= c; b -= a; b ^= (a<<8); \
  28.   c -= a; c -= b; c ^= (b>>13); \
  29.   a -= b; a -= c; a ^= (c>>12);  \
  30.   b -= c; b -= a; b ^= (a<<16); \
  31.   c -= a; c -= b; c ^= (b>>5); \
  32.   a -= b; a -= c; a ^= (c>>3);  \
  33.   b -= c; b -= a; b ^= (a<<10); \
  34.   c -= a; c -= b; c ^= (b>>15); \
  35. }
  36.  
  37. /* The golden ration: an arbitrary value */
  38. #define JHASH_GOLDEN_RATIO    0x9e3779b9
  39.  
  40. /* The most generic version, hashes an arbitrary sequence
  41.  * of bytes.  No alignment or length assumptions are made about
  42.  * the input key.
  43.  */
  44. static inline u32 jhash(const void *key, u32 length, u32 initval)
  45. {
  46.     u32 a, b, c, len;
  47.     const u8 *k = key;
  48.  
  49.     len = length;
  50.     a = b = JHASH_GOLDEN_RATIO;
  51.     c = initval;
  52.  
  53.     while (len >= 12) {
  54.         a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24));
  55.         b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24));
  56.         c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24));
  57.  
  58.         __jhash_mix(a,b,c);
  59.  
  60.         k += 12;
  61.         len -= 12;
  62.     }
  63.  
  64.     c += length;
  65.     switch (len) {
  66.     case 11: c += ((u32)k[10]<<24);
  67.     case 10: c += ((u32)k[9]<<16);
  68.     case 9 : c += ((u32)k[8]<<8);
  69.     case 8 : b += ((u32)k[7]<<24);
  70.     case 7 : b += ((u32)k[6]<<16);
  71.     case 6 : b += ((u32)k[5]<<8);
  72.     case 5 : b += k[4];
  73.     case 4 : a += ((u32)k[3]<<24);
  74.     case 3 : a += ((u32)k[2]<<16);
  75.     case 2 : a += ((u32)k[1]<<8);
  76.     case 1 : a += k[0];
  77.     };
  78.  
  79.     __jhash_mix(a,b,c);
  80.  
  81.     return c;
  82. }
  83.  
  84. /* A special optimized version that handles 1 or more of u32s.
  85.  * The length parameter here is the number of u32s in the key.
  86.  */
  87. static inline u32 jhash2(u32 *k, u32 length, u32 initval)
  88. {
  89.     u32 a, b, c, len;
  90.  
  91.     a = b = JHASH_GOLDEN_RATIO;
  92.     c = initval;
  93.     len = length;
  94.  
  95.     while (len >= 3) {
  96.         a += k[0];
  97.         b += k[1];
  98.         c += k[2];
  99.         __jhash_mix(a, b, c);
  100.         k += 3; len -= 3;
  101.     }
  102.  
  103.     c += length * 4;
  104.  
  105.     switch (len) {
  106.     case 2 : b += k[1];
  107.     case 1 : a += k[0];
  108.     };
  109.  
  110.     __jhash_mix(a,b,c);
  111.  
  112.     return c;
  113. }
  114.  
  115.  
  116. /* A special ultra-optimized versions that knows they are hashing exactly
  117.  * 3, 2 or 1 word(s).
  118.  *
  119.  * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
  120.  *       done at the end is not done here.
  121.  */
  122. static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
  123. {
  124.     a += JHASH_GOLDEN_RATIO;
  125.     b += JHASH_GOLDEN_RATIO;
  126.     c += initval;
  127.  
  128.     __jhash_mix(a, b, c);
  129.  
  130.     return c;
  131. }
  132.  
  133. static inline u32 jhash_2words(u32 a, u32 b, u32 initval)
  134. {
  135.     return jhash_3words(a, b, 0, initval);
  136. }
  137.  
  138. static inline u32 jhash_1word(u32 a, u32 initval)
  139. {
  140.     return jhash_3words(a, 0, 0, initval);
  141. }
  142.  
  143. #endif /* _LINUX_JHASH_H */
  144.